/**
 * 动态规划playground
 * 斐波拉契数列
 */

function fib(n: number): number {
    if (n === 1 || n === 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

function fibByDP(n: number): number {
    if (n < 1) return 0;
    const tmpSave: number[] = new Array(n).fill(0);

    function fibDP(n: number) {
        if (n === 1 || n === 2) return 1;
        if (tmpSave[n] > 0) return tmpSave[n];
        tmpSave[n] = fibDP(n - 1) + fibDP(n - 2);
        return tmpSave[n];
    }
    return fibDP(n);
}

function fibItera(n: number): number {
    if (n < 1) return 0;
    if (n === 1) return 1;
    const map = new Map();
    map.set(1, 1);
    map.set(2, 1);
    for (let i = 3; i <= n; i++) {
        map.set(i, map.get(i - 1) + map.get(i - 2));
    }
    return map.get(n);
}

(function () {
    console.time("fib");
    console.log("fib 40: ", fib(40));
    console.timeEnd("fib");

    console.time("fibByDP");
    console.log("fibByDP 40: ", fibByDP(40));
    console.timeEnd("fibByDP");

    console.time("fibItera");
    console.log("fibItera 40: ", fibItera(40));
    console.timeEnd("fibItera");
})();
